package interview.quicksort;

import java.util.Random;

public class QuickSort {
	Random random = new Random();
	
	public String run(String source, boolean ascending) {
		char[] array = source.toCharArray();
		if(ascending)
			quicksorta(array, 0, array.length - 1);
		else
			quicksortd(array, 0, array.length - 1);
		return new String(array);
	}
	
	public void quicksorta(char[] array, int start, int end) {
		if(end - start <= 0)
			return;
		
		int pivot = Math.abs(random.nextInt()) % (end - start + 1);
		char pivotChar = array[start + pivot];
		array[start + pivot] = array[end];
		array[end] = pivotChar;
		
		int storeIndex = start;
		for(int index = start; index < end; index++) {
			char buf;
			if(array[index] < pivotChar) {
				buf = array[storeIndex];
				array[storeIndex] = array[index];
				array[index] = buf;
				storeIndex++;
			}
		}
		
		pivotChar = array[end];
		array[end] = array[storeIndex];
		array[storeIndex] = pivotChar;
		
		quicksorta(array, start, storeIndex);
		quicksorta(array, storeIndex + 1, end);
	}

	public void quicksortd(char[] array, int start, int end) {
		if(end - start <= 0)
			return;
		
		int pivot = Math.abs(random.nextInt()) % (end - start + 1);
		char pivotChar = array[start + pivot];
		array[start + pivot] = array[end];
		array[end] = pivotChar;
		
		int storeIndex = start;
		for(int index = start; index < end; index++) {
			char buf;
			if(array[index] > pivotChar) {
				buf = array[storeIndex];
				array[storeIndex] = array[index];
				array[index] = buf;
				storeIndex++;
			}
		}
		
		pivotChar = array[end];
		array[end] = array[storeIndex];
		array[storeIndex] = pivotChar;
		
		quicksortd(array, start, storeIndex);
		quicksortd(array, storeIndex + 1, end);
	}
}
